package 二叉树;

import sun.reflect.generics.tree.Tree;

import java.util.PriorityQueue;
import java.util.TreeMap;

public class No783二叉搜索树节点最小距离 {

    /**
     * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
     * 注意：本题与 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同
     *
     * 示例 1：
     * 输入：root = [4,2,6,1,3]
     * 输出：1
     * 示例 2：
     * 输入：root = [1,0,48,null,null,12,49]
     * 输出：1
     *  
     * 提示：
     * 树中节点数目在范围 [2, 100] 内
     * 0 <= Node.val <= 105
     */

    /**
     * 注意是二叉搜索树,可以使用中序遍历
     */

    private int lastNum=Integer.MAX_VALUE;
    private int result=Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {

        midFor(root);

        return result;
    }

    private void midFor(TreeNode node) {
        if(node==null){
            return;
        }

        midFor(node.left);

        //中序
        result=Math.min(result,Math.abs(node.val-lastNum));
        lastNum=node.val;


        midFor(node.right);

    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.getNodeByArr(new Integer[]{27, null, 34, null, 58, 50, null, 44});
        treeNode.printNode();
        No783二叉搜索树节点最小距离 n=new No783二叉搜索树节点最小距离();
        int result = n.minDiffInBST(treeNode);
        System.out.println(result);
    }

}
